//
// Description: 5832. 构造元素不等于两相邻元素平均值的数组
// Created by Loading on 2021/8/15.
//

#include <bits/stdc++.h>

using namespace std;

// 排序 + 双指针
vector<int> rearrangeArray(vector<int> &nums) {
    vector<int> res;
    sort(nums.begin(), nums.end());
    for (int i = 0, j = (int) nums.size() - 1; i <= j; ++i, --j) {
        res.emplace_back(nums[i]);
        if (i != j) {
            res.emplace_back(nums[j]);
        }
    }

    return res;
}

// 随机打乱
vector<int> rearrangeArray_random(vector<int> &nums) {
    function<bool()> check = [&]() {
        for (int i = 1; i < nums.size() - 1; ++i) {
            if ((nums[i - 1] + nums[i + 1]) / 2.0 == nums[i]) {
                return false;
            }
        }
        return true;
    };
    // 获得 time-based seed
    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    // 符合要求后，停止打乱
    while (!check()) {
        // 随机打乱
        shuffle(nums.begin(), nums.end(), std::default_random_engine(seed));
    }
    return nums;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    // 排序 + 双指针
    vector<int> res = rearrangeArray(nums);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;

    // 随机打乱
    res = rearrangeArray_random(nums);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;
}